public class SegmentTree<T> {

    private T[] tree;
    private T[] data;
    private Merger<T> merger;

    public SegmentTree(T[] arr,Merger<T> merger){
        this.merger = merger;
        data = (T[])new Object[arr.length];

        for(int i=0;i<arr.length;i++){
            data[i] = arr[i];
        }

        tree = (T[])new Object[4 * arr.length];
        buildSegmenTree(0,0,data.length - 1);
    }

    private void buildSegmenTree(int treeIndex,int l,int r){
        if(l == r){
            tree[treeIndex] = data[l];
            return;
        }

        int leftIndex = leftChild(treeIndex);
        int rightIndex = rightChild(treeIndex);
        buildSegmenTree(leftIndex,l,(l+r)/2);
        buildSegmenTree(rightIndex,(l+r)/2 + 1,r);

        tree[treeIndex] = merger.merge(tree[leftIndex],tree[rightIndex]);
    }

    public int getSize(){
        return data.length;
    }

    public T get(int index){
        if(index < 0 || index >= data.length){
            throw new IllegalArgumentException("index is Illegal");
        }
        return data[index];
    }

    //返回区间[queryL,queryR]的值
    public T query(int queryL,int queryR){
        if(queryL<0 || queryL >= data.length ||
            queryR<0 || queryR >= data.length || queryL > queryR){
            throw new IllegalArgumentException("argument is Illegal");
        }

        return query(0,0,data.length-1,queryL,queryR);
    }

    private T query(int treeIndex,int l,int r,int queryL,int queryR){
        if(l == r){
            return tree[treeIndex];
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = l + (r - l) /2;

        if(queryL >= mid + 1){
            return query(rightTreeIndex,mid + 1,r,queryL,queryR);
        }else if(queryR <= mid){
            return query(leftTreeIndex,l,mid,queryL,queryR);
        }

        T leftResult = query(leftTreeIndex, l, mid, queryL, mid);
        T rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
        return merger.merge(leftResult,rightResult);
    }

    //将index位置的值，更新为e
    public void set(int index,T t){
        if(index < 0 || index >= data.length){
            throw new IllegalArgumentException("index is Illegal");
        }

        data[index] = t;
        set(0,0,data.length - 1,index,t);
    }

    private void set(int treeIndex,int l,int r,int index,T t){
        if(l == r){
            tree[treeIndex] = t;
            return;
        }

        int mid = l + (r-l)/2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        if(index >= mid + 1){
            set(rightTreeIndex,mid+1,r,index,t);
        }else if(index <= mid){
            set(leftTreeIndex,l,mid,index,t);
        }

        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return 2 * index + 1;
    }

    //返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return 2 * index + 2;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append('[');
        for(int i = 0 ; i < tree.length ; i ++){
            if(tree[i] != null)
                res.append(tree[i]);
            else
                res.append("null");

            if(i != tree.length - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}
